package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-07
 */

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class leetcode148 {
    public ListNode sortList(ListNode head) {
        if (head==null || head.next==null) return head;
        //sort
        ListNode fast=head, slow=head;
        while (fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rHead = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rHead);
        //merge
        ListNode l = new ListNode(0);
        ListNode res = l;
        while (left!=null&&right!=null){
            if (left.val<right.val){
                l.next = left;
                left = left.next;
            }else{
                l.next = right;
                right = right.next;
            }
            l = l.next;
        }
        l.next = left!=null? left:right;
        return res.next;
    }
}
